﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace NTree
{
	TEST_CLASS(P7807)
	{
		//【树的直径 离散化】 P7807 魔力滋生|普及+
		class Solution {
		public:
			vector<pair<int, int>> Ans(const int M,const int K,vector<pair<int,int>>& edge) {
				const int iOtherNeed = (0 == K) ? 2 : 0;
				vector<int> deg(M);
				for (auto& [u, v] : edge) {
					u--, v--;
					deg[u]++; deg[v]++;
				}
				vector<pair<int, int>> nedge;
				vector<int> ps;
				for (auto& [u, v] : edge) {
					if (deg[u] > deg[v]) { swap(u, v); }
					if ((1 == deg[u]) && (deg[v] > iOtherNeed)) { 
						if (0 == K)
						{
							deg[u]--, deg[v]--;
						}
						continue; 
					}
					nedge.emplace_back(u, v);
					ps.emplace_back(u);
					ps.emplace_back(v);
				}
				CDiscretize dis(ps);
				for (auto& [u, v] : nedge) {
					u = dis[u] + 1;
					v = dis[v] + 1;
				}
				return nedge;
			}
		};
	public:
		int M, K;
		vector<pair<int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			M = 2, K = 0, edge = { {1,2} };
			auto res = Solution().Ans(M, K, edge);
			AssertEx(1, (int)res.size());
		}
		TEST_METHOD(TestMethod02)
		{
			M = 2, K = 1, edge = { {1,2} };
			auto res = Solution().Ans(M, K, edge);
			AssertEx(0, (int)res.size());
		}
		TEST_METHOD(TestMethod03)
		{
			M = 4, K = 1, edge = { {1,2},{2,3},{3,4} };
			auto res = Solution().Ans(M, K, edge);
			AssertEx(1, (int)res.size());
		}
		TEST_METHOD(TestMethod11)
		{
			M = 7, K = 0,edge={ {1,2},{1,3},{1,4},{1,5},{1,6},{1,7} };
			auto res = Solution().Ans(M,K,edge);
			AssertEx(2, (int)res.size());
		}
		TEST_METHOD(TestMethod12)
		{
			M = 9, K = 1,edge={ {1,2},{2,3},{1,4},{1,5},{2,6},{2,7},{3,8},{3,9} };
			auto res = Solution().Ans(M, K, edge);
			AssertEx(2, (int)res.size());
		}
	};

	TEST_CLASS(P9369)
	{
		//P9369 [ICPC 2022 Xi'an R] Tree|普及+
		class Solution {
		public:
			int Ans(vector<int>& par) {
				par.insert(par.begin(), 0);			
				const int N = par.size();
				for (auto& i : par) { i--; }
				CParentToNeiBo pr(par);
				priority_queue<tuple<int, int, int>> maxHeap;
				function<pair<int,int>(int)> DFS = [&](int cur) {
					int iMaxLen = 1, iMaxLeafe = cur;
					for (const auto& next : pr.m_vChild[cur]) {
						auto [len, iLeafe] = DFS(next);
						if (len + 1 > iMaxLen) {
							iMaxLen = len + 1;
							iMaxLeafe = iLeafe;
						}
					}
					maxHeap.emplace(iMaxLen, cur, iMaxLeafe);
					return make_pair(iMaxLen, iMaxLeafe);
				};
				DFS(0);
				vector<bool> has(N);
				int ans = INT_MAX/2;
				int op1 = 0;
				while (maxHeap.size()) {					
					ans = min(ans,op1+get<0>(maxHeap.top()));
					auto [len, cur, iLeafe] = maxHeap.top();
					maxHeap.pop();
					has[cur] = true;
					for (auto t = iLeafe; t != cur; t = par[t]) {
						has[t] = true;
					}
					while (maxHeap.size() && (has[get<1>(maxHeap.top())])) {
						maxHeap.pop();
					}
					op1++;
				}
				ans = min(ans, op1);
				return ans;
			}
		};
	public:
		vector<int> par;
		TEST_METHOD(TestMethod01)
		{
			par = { 1,1,2,2,2,3 };
			auto res = Solution().Ans(par);
			AssertEx(3, res);			
		}
		TEST_METHOD(TestMethod02)
		{
			par = { 1,2,3,4};
			auto res = Solution().Ans(par);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod03)
		{
			par = { 1,1,1,1,1 };
			auto res = Solution().Ans(par);
			AssertEx(2, res);
		}
	};

	TEST_CLASS(P6722)
	{
		//【二分图 换根法 染色法 树的直径】P6722 「MCOI-01」Village 村庄|普及+
		class Solution {
		public:
			bool Ans(const int N ,const int K ,vector<tuple<int,int,int>>& edge) {
				auto neiBo = CNeiBo::Three(N, edge, false, 1);
				auto BFS = [&](int root) {
					vector<int> par(N, -1),dis(N,-1);
					queue<int> que;
					auto Add = [&](int cur, int iPar,int iDis) {
						if (-1 != dis[cur]) { return; }
						dis[cur] = iDis;
						par[cur] = iPar;
						que.emplace(cur);
					};
					Add(root, -1, 0);
					while (que.size()) {
						const auto cur = que.front(); que.pop();
						for (const auto& [next,w] : neiBo[cur]) {
							Add(next, cur, dis[cur] + w);
						}
					}
					return dis;
				};
				auto dis1 = BFS(0);
				const int n1 = max_element(dis1.begin(), dis1.end()) - dis1.begin();
				auto dis2 = BFS(n1);
				const int n2 = max_element(dis2.begin(), dis2.end()) - dis2.begin();
				auto dis3 = BFS(n2);
				for (int i = 0; i < N; i++) {
					if ((dis2[i] >= K) && (dis3[i] >= K)) { return false; }
				}
				return true;
			}
		};
	public:
		int N, K;
		vector<tuple<int, int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			N = 5, K = 2, edge = { {1,2,1},{2,3,1},{3,4,1},{4,5,1} };
			auto res = Solution().Ans(N,K,edge);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod02)
		{
			N = 5, K = 3, edge = { {1,2,1},{2,3,1},{3,4,1},{4,5,1} };
			auto res = Solution().Ans(N, K, edge);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod03)
		{
			N = 5, K = 8, edge = { {1,3,3},{1,2,1},{2,4,6},{2,5,2} };
			auto res = Solution().Ans(N, K, edge);
			AssertEx(true, res);
		}
		TEST_METHOD(TestMethod04)
		{
			N = 5, K = 2, edge = { {1,3,3},{1,2,1},{2,4,6},{2,5,2} };
			auto res = Solution().Ans(N, K, edge);
			AssertEx(false, res);
		}
		TEST_METHOD(TestMethod13)
		{
			N = 7, K = 4, edge = { {1,2,3},{1,3,3},{2,5,3},{2,6,3},{3,7,3},{2,4,2} };
			auto res = Solution().Ans(N, K, edge);
			AssertEx(false, res);
		}
	};

	TEST_CLASS(P10418)
	{
		//【树 链 菊花】P10418 [蓝桥杯 2023 国 A] 相连的边|普及+
		class Solution {
		public:
			long long Ans(const int N, vector<pair<int,int>>& edge) {
				vector<vector<pair<int,int>>> neiBo(N);
				for (int i = 0; i < edge.size(); i++) {
					const int u = i + 1, v = edge[i].first - 1;
					neiBo[u].emplace_back(edge[i].second,v);
					neiBo[v].emplace_back(edge[i].second,u );
				}
				long long ans = 0;
				for (auto& v : neiBo) {
					sort(v.begin(), v.end(),greater());
					if (v.size() >= 3) {
						ans = max(ans, (long long)v[0].first + v[1].first+v[2].first);
					}
				}
				for (int i = 0; i < edge.size(); i++) {
					const int u = i + 1, v = edge[i].first - 1;
					if ((neiBo[u].size() >= 2) && (neiBo[v].size() >= 2)) {
						long long cur = edge[i].second;
						cur += (v != neiBo[u][0].second )? neiBo[u][0].first : neiBo[u][1].first;
						cur += (u != neiBo[v][0].second) ? neiBo[v][0].first : neiBo[v][1].first;
						ans = max(ans, cur);
					}
				}
				return ans;
			}
		};
	public:
		int N, K;
		vector<pair< int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			N = 5, edge = { {1,1},{2,1},{3,7},{1,10} };
			auto res = Solution().Ans(N,  edge);
			AssertEx(12LL, res);
		}
	};

	TEST_CLASS(P10912)
	{
		//【图论 组合数学】P10912 [蓝桥杯 2024 国 B] 数星星|普及+
		class Solution {
		public:
			int Ans(const int N, vector<pair<int, int>>& edge, int L, int R) {
				L--, R--;
				typedef C1097Int<> BI;
				vector<int> d(N+1);
				vector<bool> vis(N+1);
				vector<BI> cnt(N);
				for (const auto&[u,v]:edge)
				{	
					d[u-1]++, d[v-1]++;
				}
				CFactorial<C1097Int<>> fac(N);
				auto Cal = [&](int d) {
					if (vis[d]) { return cnt[d]; }
					vis[d] = true;
					BI res = 0;
					for (int i = L; i <= min(R, d); i++)//对于每个i，d个点中选i-1个的结果数
						res += fac.Com(i, d);
					return cnt[d] = res;
				};
				BI ans;
				for (int i = 0; i < N; i++)
					ans += Cal(d[i]);
				if (L <= 1 && R >= 1) {
					ans -= (N-1);
				}
				return ans.ToInt();
			}
		};
	public:
		int N, L,R;
		vector<pair< int, int>> edge;
		TEST_METHOD(TestMethod01)
		{
			N = 6, L = 3, R = 4, edge = { {1,2},{1,3},{2,4},{2,5},{3,6} };
			auto res = Solution().Ans(N, edge,L,R);
			AssertEx(6, res);
		}
	};

	TEST_CLASS(P11855)
	{
		//【树 DFS BFS 离线查询】P11855 [CSP-J2022 山东] 部署|普及+
		class Solution {
		public:
			vector<int> Ans(vector<int>& a, vector<pair<int, int>>& edge, vector<tuple<int, int, int>>& ope, vector<int>& que) {
				const int N = a.size();
				auto neiBo = CNeiBo::Two(N, edge, false, 1);
				auto leves = CBFSLeve::Leve(neiBo, { 0 });
				vector<int> par(N, -1);
				for (int i = 0; i < N; i++) {
					for (const auto& next : neiBo[i]) {
						if (leves[i] < leves[next]) {
							par[next] = i;
						}	
					}
				}
				vector<int> cnt1(N), cnt2(N);
				for (auto [kind, x, y] : ope) {
					x--;
					if (2 == kind) {
						a[x] += y;
						if (-1 != par[x]) {
							a[par[x]] +=y;
						}
						cnt2[x] +=y;
					}
					else {
						cnt1[x] += y;
					}
				}
				auto leveNodes = CBFSLeve::LeveSort(leves);
				for (const auto& cur : leveNodes) {
					if (-1 != par[cur]) {
						a[cur] += cnt2[par[cur]];
						cnt1[cur] += cnt1[par[cur]];
					}
					a[cur] += cnt1[cur];
				}
				vector<int> ans;
				for (auto& q : que) {
					ans.emplace_back(a[q - 1]);
				}
				return ans;
			}
		};
	public:
		vector<int> a, que;
		vector<pair< int, int>> edge;
		vector<tuple<int, int, int>> ope;
		TEST_METHOD(TestMethod01)
		{
			que = { 1,2,3,4 }, a = { 1,2,3,4,5 }, ope = { {1,1,2},{2,2,3},{1,3,3},{2,5,1} }, edge = { {1,2},{
1,3},{2,4},{3,5} };
			auto res = Solution().Ans(a,edge,ope,que);
			AssertEx({ 6,7,9,9 }, res);
		}
		TEST_METHOD(TestMethod02)
		{
			que = { 1,2 }, a = { 1,1,1,1 }, ope = { {1,1,1} }, edge = { {1,2},{1,3},{1,4} };
			auto res = Solution().Ans(a, edge, ope, que);
			AssertEx({ 2,2 }, res);
		}
	};

	TEST_CLASS(LC3367)
	{
		//【图论 树上DP】3367. 移除边之后的权重最大和|2602
		class Solution {
		public:
			long long maximizeSumOfWeights(vector<vector<int>>& edges, int K) {
				const int N = edges.size() + 1;
				auto neiBo = CNeiBo::Three(N, edges, false);
				vector<long long> dp0(N), dp1(N);
				function<void(int, int)> DFS = [&](int cur, int par) {
					long long sum0 = 0;
					priority_queue<long long> maxHeap;
					for (const auto& [next, w]: neiBo[cur]) {
						if (next == par) { continue; }
						DFS(next, cur);
						sum0 += dp0[next];
						auto llAdd = w + dp1[next] - dp0[next];
						if (llAdd <= 0) { continue; }
						maxHeap.emplace(llAdd);
					}
					long long llCanAdd = 0;
					for (int cnt = K - 1; cnt && maxHeap.size(); cnt--, maxHeap.pop()) {
						llCanAdd += maxHeap.top();
					}
					dp0[cur] = dp1[cur] = sum0 + llCanAdd;
					if (maxHeap.size()) {
						dp0[cur] += maxHeap.top();
					}
				};
				DFS(0, -1);
				return dp0[0];
			}
		};
	public:
		vector<vector<int>> edges;
		int k;
		TEST_METHOD(TestMethod01)
		{
			edges = { {0,1,4},{0,2,2},{2,3,12},{2,4,6} }, k = 2;
			auto res = Solution().maximizeSumOfWeights(edges, k);
			AssertEx(22LL, res);
		}
		TEST_METHOD(TestMethod02)
		{
			edges = { {0,1,5},{1,2,10},{0,3,15},{3,4,20},{3,5,5},{0,6,10} }, k = 3;
			auto res = Solution().maximizeSumOfWeights(edges, k);
			AssertEx(65LL, res);
		}
	};
}
